package Algorithm.TanXin;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

//https://leetcode-cn.com/problems/course-schedule-iii/
//630. 课程表 III
//这题做错了，一开始用的 dp 来做，内存爆了
public class Leetcode630_notice_course_schedule_iii {
    class Solution {
        public int scheduleCourse(int[][] courses) {
            Arrays.sort(courses, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1]==o2[1]?o1[0]-o2[0]:o1[1]-o2[1];
                }
            });

            PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b)-> b-a);
            //优先队列中所有课程的总时间
            int total = 0;

            for(int[] course:courses){
                int ti = course[0], di = course[1];
                if(total + ti<=di){
                    total += ti;
                    q.offer(ti);
                }else if(!q.isEmpty() &&q.peek() >ti){
                    total -= q.poll() - ti;
                    q.offer(ti);
                }
            }

            return q.size();
        }
    }

    //自己的错误解法
    class Solution2 {
        public int scheduleCourse(int[][] courses) {
            Arrays.sort(courses, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1]==o2[1]?o1[0]-o2[0]:o1[1]-o2[1];
                }
            });

            int max = 0;
            int[] dp = new int[courses.length+1];
            int[][] g = new int[courses.length+1][courses.length+1];

            for(int i=1;i<courses.length+1;i++){
                for(int j=0;j<i;j++){
                    int k=0;
                    while(k<=dp[j]){
                        if(g[j][k] + courses[i-1][0]<=courses[i-1][1]){
                            if(dp[i]<=k){
                                dp[i] = k+1;
                                g[i][k+1] = g[j][k] + courses[i-1][0];
                            }else if(dp[i]==k+1){
                                g[i][k+1] = Math.min(g[i][k+1],g[j][k] + courses[i-1][0]);
                            }
                        }
                        k++;
                    }
                }
                max = Math.max(max, dp[i]);
            }

            return max;
        }
    }

}
